/*
Source : https://leetcode.com/problems/reverse-integer/
Author : nflush@outlook.com
Date   : 2016-05-09
*/
/*
20. Valid Parentheses  
Total Accepted: 107497 Total Submissions: 364633 Difficulty: Easy

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

Subscribe to see which companies asked this question
*/

bool isValid(char *s)
{
    int len = strlen(s);
    if(len == 0)
        return true;
    if(len % 2)
        return false;
    char *stack = malloc(len + 1);
    char *ps = stack;
    stack[0] = 0;
    do {
        switch(*s) {
        case '[':
            *++ps = ']';
            break;
        case '{':
            *++ps = '}';
            break;
        case '(':
            *++ps = ')';
            break;
        default:
            if(*ps != *s) {
                free(stack);
                return false;
            }
            ps--;
            break;
        }
        ++s;
    } while(*s);
    free(stack);
    return ps == stack;
}

/*
退出的条件
1:长度为 0,此时为真
2:长度为奇数,此时为假
3:各种左括号数量超过半数,此时为假
4:括号不匹配,此时为假
5:括号匹配,刚好完结,此时为真
*/
class Solution
{
public:
    bool isValid(string s)
    {
        if(s.size() == 0) return true;
        if(s.size() % 2 != 0) return false;
        vector<char> stk(s.size() + 1);
        int          len = 0;
        int          left = s.size();
        int          pos = 0;
        stk[0] = '0';
        do {
            switch(s[pos]) {
            case '[':
                stk[++len] = ']';
                break;
            case '{':
                stk[++len] = '}';
                break;
            case '(':
                stk[++len] = ')';
                break;
            default:
                if(stk[len] != s[pos]) {
                    return false;
                }
                len--;
                break;
            }
            pos++;
            left--;
        } while(left > 0 && len <= left);
        return len == 0;
    }
};